﻿namespace AdvancedTraining.Lesson35;

/// <summary>
/// 来自网易的环形分糖果问题
/// 给定一个正数数组arr，表示每个小朋友的得分
/// 任何两个相邻的小朋友，如果得分一样，怎么分糖果无所谓，但如果得分不一样，分数大的一定要比分数少的多拿一些糖果
/// 假设所有的小朋友坐成一个环形，返回在不破坏上一条规则的情况下，需要的最少糖果数
/// </summary>
public class CircleCandy
{
    /// <summary>
    /// 计算环形分糖果的最少糖果数
    /// 算法思路：
    /// 1. 找到环形数组中的局部最小值作为起点
    /// 2. 从该点开始展开成线性数组（首尾元素相同）
    /// 3. 分别计算从左到右和从右到左的糖果分配
    /// 4. 取每个位置的最大值，求和得到最终答案
    /// 时间复杂度：O(n)，空间复杂度：O(n)
    /// </summary>
    /// <param name="arr">小朋友得分数组</param>
    /// <returns>最少需要的糖果数</returns>
    public static int MinCandy(int[]? arr)
    {
        if (arr == null || arr.Length == 0) return 0;
        if (arr.Length == 1) return 1;
        var n = arr.Length;
        var minIndex = 0;
        for (var i = 0; i < n; i++)
            if (arr[i] <= arr[LastIndex(i, n)] && arr[i] <= arr[NextIndex(i, n)])
            {
                minIndex = i;
                break;
            }

        var nums = new int[n + 1];
        for (var i = 0; i <= n; i++, minIndex = NextIndex(minIndex, n)) nums[i] = arr[minIndex];
        var left = new int[n + 1];
        left[0] = 1;
        for (var i = 1; i <= n; i++) left[i] = nums[i] > nums[i - 1] ? left[i - 1] + 1 : 1;
        var right = new int[n + 1];
        right[n] = 1;
        for (var i = n - 1; i >= 0; i--) right[i] = nums[i] > nums[i + 1] ? right[i + 1] + 1 : 1;
        var ans = 0;
        for (var i = 0; i < n; i++) ans += Math.Max(left[i], right[i]);
        return ans;
    }

    private static int NextIndex(int i, int n)
    {
        return i == n - 1 ? 0 : i + 1;
    }

    private static int LastIndex(int i, int n)
    {
        return i == 0 ? n - 1 : i - 1;
    }

    /// <summary>
    /// 运行测试用例
    /// </summary>
    public static void Run()
    {
        Console.WriteLine("=== 环形分糖果问题测试 ===");

        // 测试用例1：基本功能测试
        TestBasicFunctionality();

        // 测试用例2：单个元素
        TestSingleElement();

        // 测试用例3：所有元素相同
        TestAllSameElements();

        // 测试用例4：递增序列
        TestIncreasingSequence();

        // 测试用例5：递减序列
        TestDecreasingSequence();

        // 测试用例6：复杂情况
        TestComplexCase();
    }

    private static void TestBasicFunctionality()
    {
        int[] arr = [3, 4, 2, 3, 2];
        int result = MinCandy(arr);
        Console.WriteLine($"测试1 - 基本功能: [3,4,2,3,2] -> {result} (期望: 9)");
    }

    private static void TestSingleElement()
    {
        int[] arr = [5];
        int result = MinCandy(arr);
        Console.WriteLine($"测试2 - 单个元素: [5] -> {result} (期望: 1)");
    }

    private static void TestAllSameElements()
    {
        int[] arr = [3, 3, 3, 3];
        int result = MinCandy(arr);
        Console.WriteLine($"测试3 - 所有元素相同: [3,3,3,3] -> {result} (期望: 4)");
    }

    private static void TestIncreasingSequence()
    {
        int[] arr = [1, 2, 3, 4, 5];
        int result = MinCandy(arr);
        Console.WriteLine($"测试4 - 递增序列: [1,2,3,4,5] -> {result} (期望: 15)");
    }

    private static void TestDecreasingSequence()
    {
        int[] arr = [5, 4, 3, 2, 1];
        int result = MinCandy(arr);
        Console.WriteLine($"测试5 - 递减序列: [5,4,3,2,1] -> {result} (期望: 15)");
    }

    private static void TestComplexCase()
    {
        int[] arr = [2, 2, 1, 2, 2, 2, 1];
        int result = MinCandy(arr);
        Console.WriteLine($"测试6 - 复杂情况: [2,2,1,2,2,2,1] -> {result}");
    }
}